#include <cstdio>
#include <vector>
using namespace std;

namespace Floyd 
{
struct FloydResult 
{
    vector<vector<int>> dist;
    vector<vector<int>> prev;
};

FloydResult floyd(vector<vector<int>>& graph)
{
    int n = graph.size();
    vector<vector<int>> dist(graph);
    vector<vector<int>> prev(n, vector<int>(n, -1));

    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n; ++j) 
            if (graph[i][j] >= 0 && i != j)
                prev[i][j] = i;

    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
            {
                if (dist[k][j] < 0 || dist[i][k] < 0)
                    continue;
                if (dist[i][j] < 0 || dist[i][j] > dist[i][k] + dist[k][j]) 
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    prev[i][j] = k;
                }
            }
    return {dist, prev};
}

};
int main(int argc, char** argv)
{
    int INF = -1;
    vector<vector<int>> graph = 
    { {0, 2, 5, INF, INF}, 
      {INF, 0, 2, 6, INF}, 
      {INF, INF, 0, 7, 1}, 
      {INF, INF, 2, 0, 4},
      {INF, INF, INF, INF, 0} };
    auto result = Floyd::floyd(graph);
    for (int i = 0; i < result.dist.size(); ++i)
    {
        for (int j = 0; j < result.dist[i].size(); ++j)
            printf("%d ", result.dist[i][j]);
        printf("\n");
    }
    return 0;
}
